package leetcode_题库;

import java.util.List;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/27 17:02 星期六
 */
public class _104_二叉树的最大深度 {
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;

        int nn = maxDepth(n1);
        System.err.println(nn);
    }

    /**
     * 深度优先计算最大深度
     * > 2022/08/27 17:11:31
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:41.3 MB,击败了46.07% 的Java用户
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        return dfs(root,0);
    }

    private static int dfs(TreeNode n, int i) {
        if (n == null){
            //若n为空，返回i（原封不动返回去）
            return i;
        }
        //否则，递归比较该结点的左右子结点深度，并+1层
        return Math.max(dfs(n.left,i),dfs(n.right,i)) + 1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
